Multicast virtual circuit networks of the prior art support communication paths from a sender to an arbitrary number of receivers, as illustrated in FIG. 1. As shown, multicast virtual circuits induce a tree in a network connecting a sender to one or more receivers. Switching systems participating in the virtual circuit replicate received cells using virtual circuit identifiers in the cell headers to access control information stored in the switching system's internal control tables, then use this information to identify the outputs the cells are to be sent to and relabel the copies before forwarding them on to other switching systems.
FIG. 2 illustrates in more detail the function of a multicast virtual circuit switch. The switch includes control information, shown here as a table, which for each incoming virtual circuit provides a list of outputs and outgoing virtual circuit identifiers. For a cell received on input link i and virtual circuit z, the switch forwards copies to outputs j.sub.1, j.sub.2, . . . after relabeling them with new virtual circuit identifiers, y.sub.1, y.sub.2, . . . Notice that if the switch has n inputs and outputs and each output supports up to m virtual circuits, one can describe any collection of multicast virtual circuits with mn words of memory. One simply provides for each (output, VCI) pair, the identity of the (input, VCI) pair from which it is to receive cells. Unfortunately, this method of defining a set of multicast connections is not particularly helpful in switching, as it does not give one a way to go from an (input, VCI) pair to the desired list of (output, VCI) pairs. Existing virtual circuit switch architectures describe multicast virtual circuits in different ways, which while suitable for switching, use far more than mn words of memory. The switch disclosed in the inventor's prior U.S. Pat. No. 4,734,907, for example, requires mn.sup.2 /2 words of memory under worst-case conditions. Moreover, the time required to update a multicast connection grows with the size of the connection.
As an improvement over this prior implementation of multicasting, the present invention has been developed which describes a multicast switch architecture with O(n log n) hardware complexity that is nonblocking, in the sense that it is always possible to accommodate a new multicast connection or augment an existing one, so long as the required bandwidth is available at the external links, and which requires &lt;2 mn words of memory for multicast address translation. Moreover, the overhead for establishing or modifying a multicast connection is independent of the size of the connection or the switching network. In essence, the present invention relies upon a recycling and "copy-by-two" function creating extra copies or duplicate copies of data cells for routing to the multicast connection. By making multiple passes or recycles of the data cell through the same switch fabric, logical "trees" are set up which branch by two on each pass. The inventor has developed a methodology for adding and dropping multicast connections which provide for structuring of the "tree" to thereby minimize memory requirements and switch bandwidth requirements. In recognition of the fact that data cells will undoubtedly get out of sequence, resequencing buffers are provided and may be implemented either as the cells finally exit the switch fabric or, additionally, as the cells are recycled back through the switch fabric. These resequencers place the data cells back in order so as to ensure the integrity of the data stream.
While a specific implementation of this recycling for multicast connection methodology is disclosed, it should be understood that it may be implemented in a wide variety of switch architectures in order to add multicasting capability.
While the principal advantages and features of the present invention have been described above, a more complete and thorough understanding of the invention may be attained by referring to the drawings and description of the preferred embodiment which follow.